In multiprocessing systems, plural service requests may often be concurrently pending for a single service. A typical example of such concurrently pending service requests are multiple fetch requests for an empty memory location. The problem presented by such service requests is one of synchronization. Each service request must be granted access to the service in a synchronized manner.
One prevalent approach utilized with data flow processing systems to remedy the problem of synchronizing fetch requests is the use of I-structures. The I-structures provide a mechanism wherein pending fetch requests can be added on to a deferred list while waiting for a value to be written into the memory location. In particular, each memory location contains a state field that indicates the current state of the memory location. If multiple requests are pending for an empty memory location, the memory location is put into a deferred state and points to a deferred list of fetch requests. These fetch requests are serviced when a write request arrives to the memory location. I-structures are discussed in more detail in Arvind and R. E. Thomas, I-Structures an Efficient Data Type for Parallel Machines, technical memo TM-187, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Mass., September 1980.